package com.mlh.greed;

/**
 * @author 缪林辉
 * @date 2024/4/10 11:48
 * @DESCRIPTION
 */
// 给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
// 每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
// 0 <= j <= nums[i]
// i + j < n
// 返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

// 跳跃游戏是问能不能到达  这个则是能到达，但是要选择最小的跳数
public class 跳跃游戏2 {
    // 贪心策略 和跳跃游戏的贪心策略一样  我的代码稍微改一下就能解决这题了
    //代码随心录的不行 他的实现和这题差的有点多
    public int jump(int[] nums) {
        if(nums.length<=1){
            return 0;
        }
        int site=0;
        int jumpNum=1;
        while (site+nums[site]<nums.length-1){
            int max=0;
            int maxIndex=-1;
            //选取该跳范围内能够跳到最远位置 的位置
            for (int i = 1; i <=nums[site]&&site+i<nums.length; i++) {
                if (site + i+nums[site + i] > max) {
                    max = site + i+nums[site + i];
                    maxIndex=site + i;
                }
            }
            //如果发现该跳范围内能够跳到最远位置还是在该跳范围内，那说明跳不出去了，返回false
            site=maxIndex;
            //在这里记录跳数
            jumpNum++;
        }
        return jumpNum;
    }

    //用覆盖范围理解
    //你跳到一处他的覆盖范围更广肯定比覆盖范围小的好
    //因为你比他有更多的选择，你已经包括他了
    //不要想着什么最远一跳可能会跳到nums[i]=0
    //最远一跳不是说他一定要跳到最远处
    //而是他能覆盖的范围最广，可以选择的最多
    public int practice(int[] nums) {
        if(nums.length<=1){
            return 0;
        }
        int cover=nums[0];
        int start=0,end=cover;
        boolean flag=true;
        int stepNum=0;
        while(flag&&cover<nums.length-1){
            flag=false;
            for (int i = start; i <=end ; i++) {
                flag=true;
                cover=Math.max(cover,i+nums[i]);
            }
            start=end+1;
            end=cover;
            stepNum++;
        }
        return stepNum+1;
    }
}
